#include "bin_packing.h"

namespace Packing_common
{
	Bin_packing_2::Bin_packing_2(const Rectangular_box& container) : box(container)
	{
		terrace.push_back(H_seg(box.x_min(), box.x_max(), box.y_min()));
		x_sorted.push_back(terrace.begin());
		y_sorted.push_back(terrace.begin());

		cut_height = (box.y_max() - box.y_min());
	}
	bool Bin_packing_2::put_one_bin(const Iso_rectangle_2& bin, double& pos_x, double& pos_y) 
	{			
		while (true)
		{
			// search from bottom to top for a platform segment that can hold this bin
			std::list<H_seg_iter>::iterator it;
			for (it = y_sorted.begin(); it != y_sorted.end(); ++it)
			{
				if ((*it)->contain(bin.xmin(), bin.xmax()))
				{
					// align left-bottom corner
					pos_x = (*it)->left - bin.xmin();
					pos_y = (*it)->height - bin.ymin(); 
					if ( bin.xmax() - bin.xmin() == (*it)->length() ) // coincidence of equal length
					{
						(*it)->height += (bin.ymax()-bin.ymin());
						for (std::list<H_seg_iter>::iterator rit = it; rit != y_sorted.end(); ++rit)
							if ((*it)->height > (*rit)->height)
								std::swap(*it, *rit);
					}
					else // one more new segment
					{
						double sep_x = (*it)->left + (bin.xmax()-bin.xmin());
						terrace.push_back(H_seg((*it)->left, sep_x, (*it)->height + (bin.ymax() - bin.ymin())));
						(*it)->left = sep_x;
						// insert the new segment in the y-sorted list, it must be after y_sort[i]
						H_seg_iter h = terrace.end();
						--h;
						std::list<H_seg_iter>::iterator cit;
						for (cit = it; cit != y_sorted.end(); ++cit)
							if ((*cit)->height > h->height)
								break;
						y_sorted.insert(cit, h);
						std::list<H_seg_iter>::iterator x_sort_place = std::find(x_sorted.begin(), x_sorted.end(), *it);
						x_sorted.insert(x_sort_place, h);
					}
					if (merge())
					{
						// update y-sorted list
						y_sorted.clear();
						std::copy(x_sorted.begin(), x_sorted.end(), std::back_inserter< std::list<H_seg_iter> >(y_sorted));
						y_sorted.sort(y_order_cmp());
					}
					// whether some go too high
					if ( bin.ymax() + pos_y >= cut_height)
					{
						liftup();
						cut_height += 0.5*(box.y_max()-box.y_min());
					}
					return true;
				}
			}
			if (it == y_sorted.end() && terrace.size() == 1) // cannot find suitable place and no segments to be merged
				return false;

			// no suitable place found, merge some segments, from lower to higher
			liftup();
		}
	}

	void Bin_packing_2::clear()
	{
		terrace.clear(); 
		x_sorted.clear();
		y_sorted.clear();
	}

	bool Bin_packing_2::liftup()
	{
		std::list<H_seg_iter>::iterator std_height = y_sorted.begin();
		bool no_merge_last_time = true;  // if nothing is merged last time, we must make platform higher until merge occurs or no possible merge
		while (no_merge_last_time && terrace.size() > 1)
		{
			++std_height;
			for (std::list<H_seg>::iterator oit = terrace.begin(); oit != terrace.end(); ++oit)
				oit->height = std::max((*std_height)->height, oit->height);
				
			no_merge_last_time = !merge();
		}
				
		// update y-sorted list
		if (!no_merge_last_time)
		{
			y_sorted.clear();
			std::copy(x_sorted.begin(), x_sorted.end(), std::back_inserter< std::list<H_seg_iter> >(y_sorted));
			y_sorted.sort(y_order_cmp());
		}

		return !no_merge_last_time;
	}
	bool Bin_packing_2::merge()
	{
		bool merge_happen = false;
		std::list<H_seg_iter>::iterator cur = x_sorted.begin();
		while (true)
		{
			std::list<H_seg_iter>::iterator nxt = cur;
			++nxt;
			if (nxt == x_sorted.end())
				break;
			if ((*nxt)->height == (*cur)->height) // identical height, merge
			{
				(*cur)->right = (*nxt)->right;
				terrace.erase(*nxt);			
				x_sorted.erase(nxt);
				merge_happen = true;
			}
			else
				++cur;
		}
		return merge_happen;
	}

}